
21
For f(n) = Ω(g(n)), g(n) is a lower bound function and there may be
several such functions, but it is appropriate that is the function
which is almost as large a function of n is possible such that the
definition of Ω is satisfied and is chosen as g(n).
1.5.2 Theta Notation (Ѳ)
The theta notation is used when the function f(n) is bounded
both from above and below by the function g(n).
Definition: f(n) = Ѳ (g(n)), iff there exists a positive constants c1
and c2, and a positive integer n0 such that c1|g(n)| < |f(n)| <
c2|g(n)|, for all n>n0.
From the definition it implies that the function g(n) is both an upper
bound and a lower bound for the function f(n) for all values of n,
n>n0. In other words,f(n) is such that, f(n)=O(g(n)) and f(n) =
Ω(g(n))
For f(n) = 18n + 9, since f(n) > 18n and f(n) < 27n for n > 1, we
have f(n) = Ω(n) and therefore f(n) = O(n) respectively, for n > 1.
Hence f(n) = Ѳ (n).
1.5.3 Small Oh Notation(o)
Definition: f(n)=o(g(n)) iff f(n)=O(g(n)) and f(n)≠ Ω(g(n)). For
f(n)=18n+9, we have f(n)=O(n
2
) but f(n)≠ Ω(n
2
).Hence f(n) = o(n
2
).
However f(n) ≠ o(n).
Exercise:
1. Explain the insertion sort. Discuss its time and space complexity.
2. Sort the sequence 3,1,4,1,5,9,2,6,5 using insertion sort.
3. Explain Bubble sort with its analysis.
4. Explain the algorithm for shell sort.
5. Show the result of running Shellsort on the input 9,8,7,6,5,4,3,2,1
using increments {1,3,7}.
6. Write a program to implement selection algorithm.
7.Show how heapsort processes the input
142,543,123,65,453,879,572,434,111,242,811,102.
8.Using the radix sort, determine the running of radix sort.